/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    let res = [];
    partitionLevel(s, res, [], 0)
    return res
};

function partitionLevel(s, res, valArr, index) {
    if (index === s.length) {
        res.push([...valArr])
        return
    }

    // 切割字符串的所有情况
    for (let i = index; i < s.length; i++) {
        // 每次从index处切割1-2-3-s.length-1个字符
        let str = s.substr(index, i - index + 1),
            bool = isHui(str);
        if (bool) {
            valArr.push(str)
        } else {
            continue
        }
        partitionLevel(s, res, valArr, i + 1)
        if (bool) {
            valArr.pop()
        }
    }
}


function isHui(s, left = 0, right = s.length - 1) {
    while (left <= right) {
        if (s[left] !== s[right]) return false
        left++
        right--
    }
    return true
}